package com.company;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Main {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    static List<TreeNode>result = new ArrayList<>();

    public static LinkedList<TreeNode>_generateTrees(int start,int end){
        LinkedList<TreeNode>allTrees = new LinkedList<TreeNode>();
        if(start>end){
            allTrees.add(null);
            return allTrees;
        }

        for(int i=start;i<=end;i++){
            LinkedList<TreeNode>left = _generateTrees(start,i-1);
            LinkedList<TreeNode>right = _generateTrees(i+1,end);

            for(TreeNode m:left){
                for(TreeNode n:right){
                    TreeNode mid = new TreeNode(i);
                    mid.left = m;
                    mid.right = n;
                    allTrees.add(mid);
                }
            }
        }
        return allTrees;
    }

    public static List<TreeNode> generateTrees(int n) {
        if(n == 0)return new ArrayList<>();
        return _generateTrees(1,n);
    }
    public static void main(String[] args) {
	// write your code here

    System.out.println();
    }
}
